Manual Big-O Analysis
Time: O(n) • Space: O(1)
Why: One level of looping detected; typical single pass suggests O(n) time and O(1) space. These are heuristics; empirical results below provide a practical check.
Time: O(log • Space: O(log
Why: Detected divide-and-conquer hints (index halving, slicing, floor division by 2). This suggests logarithmic time. If implemented recursively, expect O(log n) stack space; iterative implementations usually use O(1) extra space. These are h...
Beginner & Interview Summaries
When the input size n doubles, the runtime grows by approximately 4.83×, which suggests performance closest to O(n log n).
Interview: brute_force_sort has an estimated time complexity of O(n) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
When the input size n doubles, the runtime grows by approximately 1.26×, which suggests performance closer to O(log n).
Interview: merge_sort has an estimated time complexity of O(log n) and space complexity of O(log n). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
Runtime Chart
Runtime Table (mean ± 95% CI)
| n | brute_force_sort | merge_sort |
|---|---|---|
| 3 | 1.36 µs ± 309.64 ns | 2.37 µs ± 109.91 ns |
| 4 | 2.73 µs ± 520.26 ns | 3.49 µs ± 85.02 ns |
| 5 | 6.33 µs ± 4.06 µs | 4.72 µs ± 215.10 ns |
| 6 | 33.49 µs ± 21.85 µs | 5.67 µs ± 128.50 ns |
| 7 | 247.95 µs ± 238.54 µs | 6.52 µs ± 272.47 ns |
| 8 | 1.77 ms ± 1.51 ms | 7.48 µs ± 338.00 ns |
Peak Memory Chart
Memory Table (mean ± 95% CI)
| n | brute_force_sort | merge_sort |
|---|---|---|
| 3 | 609.60 B ± 109.11 B | 204.80 B ± 5.44 B |
| 4 | 1.10 KB ± 613.21 B | 225.60 B ± 4.44 B |
| 5 | 1.93 KB ± 1.57 KB | 264.00 B ± 7.02 B |
| 6 | 776.00 B ± 777.28 B | 209.60 B ± 26.65 B |
| 7 | 868.80 B ± 901.64 B | 236.80 B ± 5.44 B |
| 8 | 560.00 B ± 0.00 B | 235.20 B ± 5.44 B |
Comparison Summary
Best/worst runtime at each n (lower is better). Mean ranks summarize performance across all n.
| n | Best Runtime | Worst Runtime | Mean Ranks |
|---|---|---|---|
| 3 | brute_force_sort | merge_sort | brute_force_sort: 1.67 merge_sort: 1.33 |
| 4 | brute_force_sort | merge_sort | brute_force_sort: 1.67 merge_sort: 1.33 |
| 5 | merge_sort | brute_force_sort | brute_force_sort: 1.67 merge_sort: 1.33 |
| 6 | merge_sort | brute_force_sort | brute_force_sort: 1.67 merge_sort: 1.33 |
| 7 | merge_sort | brute_force_sort | brute_force_sort: 1.67 merge_sort: 1.33 |
| 8 | merge_sort | brute_force_sort | brute_force_sort: 1.67 merge_sort: 1.33 |
Mean Runtime Comparison (bar)
Bar chart placeholder: you can render an additional Plotly bar chart here comparing means per function.
Methods & Notes
- Runtime measured with
time.perf_counter(); each (function, n) pair ran 5 times after 2 warmup iterations. GC was enabled and collected before runs. - Memory peak measured with
tracemallocbackend (tracemallocby default). - Confidence Intervals: T at 95% confidence. T-intervals use standard t critical values; bootstrap uses 2,000 resamples with a fixed seed.
- Reference curves (O(1), O(log n), O(n), O(n log n), plus any custom) were normalized at the largest n to match the average observed runtime scale.